During the process of writing data into memory, the data is often encoded with extra bits (“parity bits”) to form a codeword. In the presence of noise, some of the bits representing the codeword may change, corrupting the original codeword with errors. When the codeword is read from the memory, a decoder may be used to identify and correct the errors using error correction coding (ECC). For example, Bose-Chaudhuri-Hocquenghem (BCH) ECC schemes are used in applications where bit errors tend to be uncorrelated. An error correction capability of an ECC scheme tends to increase as the length of the codewords increases. As a result, ECC schemes implemented in data storage systems and communication devices tend to use longer codewords.
BCH decoding can be performed in multiple sequential stages to correct errors in received data. For example, a BCH decoder can generate syndrome components for a received codeword that may include errors. The BCH decoder can generate a key equation (e.g. an error location polynomial) may be generated based on the computed syndromes and may indicate a number of errors detected in the received codeword. Locations of the detected errors within the received codeword may be determined based on roots of the key equation via an iterative process such as a Chien search. Since the Chien search process is typically preformed sequentially on each value in the received codeword, an amount of time to process the codeword may be proportional to the codeword length. As codeword lengths increase, delays caused by Chien search processing can impose limits on the speed of ECC data correction.